

//给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "bcabc"
//输出："abc"
// 
//
// 示例 2： 
//
// 
//输入：s = "cbacdcbc"
//输出："acdb" 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 由小写英文字母组成 
// 
//
// 
//
// 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct
//-characters 相同 
// Related Topics 栈 贪心 字符串 单调栈 
// 👍 692 👎 0


import java.util.Stack;

/**
 * 316.去除重复字母.remove-duplicate-letters
 *
 * @author orz
 * @since 2022-03-26 14:58:22
 **/

class Solution_316 {
    public static void main(String[] args) {
        Solution solution = new Solution_316().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            Stack<Character> stack = new Stack<>();
            boolean[] inStack = new boolean[128];
            int[] count = new int[128];
            char[] chars = s.toCharArray();
            for (char item : chars) {
                count[item]++;
            }
            for (char item : chars) {
                count[item]--;
                if(inStack[item]){
                    continue;
                }
                // 插入之前，和前面的元素比一下大小。如果比之前的元素小，就将之前的元素pop出栈
                while (!stack.isEmpty() && stack.peek() > item){
                    if(count[stack.peek()] == 0){
                        break;
                    }
                    // 弹出栈顶的元素，并且标记它为不在栈中
                    inStack[stack.pop()] = false;
                }

                //如果不在栈里面，就加入到栈
                stack.push(item);
                inStack[item] = true;
            }

            StringBuilder result = new StringBuilder();
            while(!stack.isEmpty()){
                result.append(stack.pop());
            }
            return result.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}